package org.example.everyday;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/2/17 9:56
 */
public class Lc688 {
    static int[][] dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k + 1][n][n];
        for(int step = 0; step <= k; step++){
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(step == 0){
                        dp[step][i][j] = 1;
                    }else{
                        for(int[] dir :dirs){
                            int ni = i +dir[0],nj = j +dir[1];
                            if(ni >= 0 && ni < n && nj >= 0 && nj < n){
                                dp[step][i][j] += dp[step - 1][ni][ni]/8;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }




}
